#include <iostream>
#include <vector>

using namespace std;

struct TreeNode 
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() 
		:val(0)
		,left(nullptr)
		,right(nullptr) 
	{}
	TreeNode(int x) 
		:val(x)
		,left(nullptr)
		,right(nullptr) 
	{}
	TreeNode(int x, TreeNode* left, TreeNode* right) 
		:val(x)
		,left(left)
		,right(right) 
	{}
};
class Solution 
{
public:
	int dfs(TreeNode* root, int val)
	{
		if (!root)
			return 0;
		val = (val << 1) | root->val;
		if (!root->left && !root->right)
			return val;
		return dfs(root->left, val) + dfs(root->right, val);
	}

	int sumRootToLeaf(TreeNode* root)
	{
		return dfs(root, 0);
	}
};

int main()
{
	TreeNode* C = new TreeNode(0);
	TreeNode* D = new TreeNode(1);
	TreeNode* E = new TreeNode(0);
	TreeNode* F = new TreeNode(1);
	TreeNode* A = new TreeNode(0, C, D);
	TreeNode* B = new TreeNode(1, E, F);
	TreeNode* root = new TreeNode(1, A, B);

	A->left = C;
	A->right = D;
	B->left = E;
	B->right = F;

	Solution xz;
	int n = xz.sumRootToLeaf(root);
	cout << n << endl;
	return 0;
}